/*
 * @FilePath: /data-and-structure-lv/13/rbtree.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2022-01-01 13:38:46
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2022-01-01 18:19:01
 */
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>

typedef int ElementType;

#define BASE_POINT (2 * 3)
#define TOTAL_HEIGHT 3
#define ADJUST_FACTOR 2
#define REFERENCE_DISTANCE 90

typedef int ElementType;

typedef enum Color_Tag
{
    BLACK,
    RED
} Color;

typedef struct RbNode_Tag
{
    ElementType value;
    Color color;
    struct RbNode_Tag *parent;
    struct RbNode_Tag *left;
    struct RbNode_Tag *right;
} RbNode;

static RbNode EMPTY_RBNODE = {.value = INT_MIN, .color = BLACK};

typedef struct RbTree_Tag
{
    /* data */
    RbNode *root;
    RbNode *nil;
} RbTree;

typedef RbNode *PointObj;
typedef struct PointHight_Tag
{
    PointObj point;
    int offset;
    struct PointHight_Tag *next;
} PointHight;
typedef struct PointHightList_Tag
{
    int treeHeight;
    int height;
    PointHight *pointHight;
    struct PointHightList_Tag *next;
} PointHightList;

RbTree *init_rbtree()
{
    RbTree *newRbTree = malloc(sizeof(RbTree));
    newRbTree->nil = &EMPTY_RBNODE;
    newRbTree->nil->parent = &EMPTY_RBNODE;
    newRbTree->nil->left = &EMPTY_RBNODE;
    newRbTree->nil->right = &EMPTY_RBNODE;
    newRbTree->root = newRbTree->nil;
}

void release_rbnode(RbTree *rbtree, RbNode *rbnode, int isDown)
{
    if (isDown)
    {
        if (rbnode->left != rbtree->nil)
        {
            release_rbnode(rbtree, rbnode->left, isDown);
        }
        if (rbnode->right != rbtree->nil)
        {
            release_rbnode(rbtree, rbnode->right, isDown);
        }
    }
    if (rbnode != rbtree->nil)
    {
        free(rbnode);
    }
}
void release_rbtree(RbTree *rbtree)
{
    release_rbnode(rbtree, rbtree->root, 1);
    free(rbtree);
}

RbNode *create_rbnode(ElementType value)
{
    RbNode *newRbNode = malloc(sizeof(RbNode));
    newRbNode->value = value;
    newRbNode->color = RED;
    newRbNode->parent = &EMPTY_RBNODE;
    newRbNode->left = &EMPTY_RBNODE;
    newRbNode->right = &EMPTY_RBNODE;
}

void left_rotate(RbTree *rbtree, RbNode *x)
{
    RbNode *y = x->right;
    x->right = y->left;
    if (y->left != rbtree->nil)
    {
        /* code */
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == rbtree->nil)
    {
        rbtree->root = y;
    }
    else if (x == x->parent->left)
    {
        x->parent->left = y;
    }
    else
    {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

void right_rotate(RbTree *rbtree, RbNode *x)
{
    RbNode *y = x->left;
    x->left = y->right;
    if (y->right != rbtree->nil)
    {
        /* code */
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == rbtree->nil)
    {
        rbtree->root = y;
    }
    else if (x == x->parent->right)
    {
        x->parent->right = y;
    }
    else
    {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

void rb_insert_fixup(RbTree *rbtree, RbNode *z)
{
    while (z->parent->color == RED)
    {
        if (z->parent == z->parent->parent->left)
        {
            RbNode *y = z->parent->parent->right;
            if (y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else if (z == z->parent->right)
            {
                z = z->parent;
                left_rotate(rbtree, z);
            }
            else
            {
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(rbtree, z->parent->parent);
            }
        }
        else
        {
            RbNode *y = z->parent->parent->left;
            if (y->color == RED)
            {
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            }
            else if (z == z->parent->left)
            {
                z = z->parent;
                right_rotate(rbtree, z);
            }
            else
            {
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                left_rotate(rbtree, z->parent->parent);
            }
        }
    }
    rbtree->root->color = BLACK;
}

void rb_insert(RbTree *rbtree, RbNode *z)
{
    RbNode *y = rbtree->nil;
    RbNode *x = rbtree->root;
    while (x != rbtree->nil)
    {
        y = x;
        if (z->value < x->value)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    z->parent = y;
    if (y == rbtree->nil)
    {
        rbtree->root = z;
    }
    else if (z->value < y->value)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }
    z->left = rbtree->nil;
    z->right = rbtree->nil;
    z->color = RED;
    rb_insert_fixup(rbtree, z);
}

void rb_transplant(RbTree *rbtree, RbNode *u, RbNode *v)
{
    if (u->parent == rbtree->nil)
    {
        rbtree->root = v;
    }
    else if (u == u->parent->left)
    {
        u->parent->left = v;
    }
    else
    {
        u->parent->right = v;
    }
    v->parent = u->parent;
}

RbNode *tree_minimum(RbNode *x)
{
    while (x->left != &EMPTY_RBNODE)
    {
        x = x->left;
    }
    return x;
}

void rb_delete_fixup(RbTree *rbtree, RbNode *x)
{
    while (x != rbtree->root && x->color == BLACK)
    {
        if (x == x->parent->left)
        {
            RbNode *w = x->parent->right;
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                left_rotate(rbtree, x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK)
            {
                /* code */
                w->color = RED;
                x = x->parent;
            }
            else if (w->right->color == BLACK)
            {
                w->left->color = BLACK;
                w->color = RED;
                right_rotate(rbtree, w);
            }
            else
            {
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                left_rotate(rbtree, x->parent);
                x = rbtree->root;
            }
        }
        else
        {
            RbNode *w = x->parent->left;
            if (w->color == RED)
            {
                w->color = BLACK;
                x->parent->color = RED;
                right_rotate(rbtree, x->parent);
                w = x->parent->left;
            }
            if (w->left->color == BLACK && w->right->color == BLACK)
            {
                /* code */
                w->color = RED;
                x = x->parent;
            }
            else if (w->left->color == BLACK)
            {
                w->right->color = BLACK;
                w->color = RED;
                left_rotate(rbtree, w);
            }
            else
            {
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                right_rotate(rbtree, x->parent);
                x = rbtree->root;
            }
        }
    }
    x->color = BLACK;
}

void rb_delete(RbTree *rbtree, RbNode *z)
{
    RbNode *y = z;
    RbNode *x;
    Color y_original_color = y->color;
    if (z->left == rbtree->nil)
    {
        x = z->right;
        rb_transplant(rbtree, z, z->right);
    }
    else if (z->right == rbtree->nil)
    {
        x = z->left;
        rb_transplant(rbtree, z, z->left);
    }
    else
    {
        y = tree_minimum(z->right);
        y_original_color = y->color;
        x = y->right;
        if (y->parent == z)
        {
            x->parent = y;
        }
        else
        {
            rb_transplant(rbtree, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        rb_transplant(rbtree, z, y);
        y->left = z->left;
        y->left->parent = y;
        y->color = z->color;
    }
    if (y_original_color == BLACK)
    {
        rb_delete_fixup(rbtree, x);
    }
}

void record_child(RbNode *root, PointHightList *head, PointHightList *prev, int height, int reference_distance)
{
    RbNode *left = root->left;
    RbNode *right = root->right;
    if (left == &EMPTY_RBNODE && right == &EMPTY_RBNODE)
    {
        return;
    }

    PointHightList *headtemp = head;
    PointHightList *curlist = NULL;
    for (int i = 0; i < height; i++)
    {
        if (headtemp->next == NULL && i == (height - 1))
        {
            /* code */
            curlist = malloc(sizeof(PointHightList));
            curlist->height = height;
            head->treeHeight = fmax(height, head->height);
            headtemp->next = curlist;
            break;
        }
        headtemp = headtemp->next;
    }
    if (curlist == NULL)
    {
        curlist = headtemp;
    }

    if (left != &EMPTY_RBNODE)
    {
        PointHight *pointHightLeft = malloc(sizeof(PointHight));
        pointHightLeft->point = left;
        pointHightLeft->offset = reference_distance - (TOTAL_HEIGHT - height) * BASE_POINT * ADJUST_FACTOR - 2 * BASE_POINT;
        pointHightLeft->next = NULL;
        PointHight *temp = curlist->pointHight;
        if (temp != NULL)
        {
            for (; temp->next != NULL;)
            {
                temp = temp->next;
            }
            temp->next = pointHightLeft;
        }
        else
        {
            curlist->pointHight = pointHightLeft;
        }

        record_child(left, head, curlist, height + 1, pointHightLeft->offset);
    }

    if (right != &EMPTY_RBNODE)
    {

        PointHight *pointHightRight = malloc(sizeof(PointHight));
        pointHightRight->point = right;
        pointHightRight->offset = reference_distance + (TOTAL_HEIGHT - height) * BASE_POINT * ADJUST_FACTOR + 2 * BASE_POINT;
        pointHightRight->next = NULL;
        PointHight *temp = curlist->pointHight;
        if (temp != NULL)
        {
            for (; temp->next != NULL;)
            {
                temp = temp->next;
            }
            temp->next = pointHightRight;
        }
        else
        {
            curlist->pointHight = pointHightRight;
        }
        record_child(right, head, curlist, height + 1, pointHightRight->offset);
    }
}

void print_array_to_tree(RbNode *root)
{
    int height = 0;
    PointHightList *list = malloc(sizeof(PointHightList));
    list->height = height;
    list->treeHeight = height;

    PointHight *pointHight = malloc(sizeof(PointHight));
    pointHight->point = root;
    pointHight->offset = REFERENCE_DISTANCE;
    pointHight->next = NULL;
    list->pointHight = pointHight;

    list->next = NULL;
    record_child(root, list, list, height + 1, REFERENCE_DISTANCE);

    int lastOffset = 0;
    PointHightList *listTemp = list;
    while (listTemp != NULL)
    {
        PointHight *curPoint = listTemp->pointHight;
        lastOffset = 0;
        while (curPoint != NULL)
        {

            lastOffset = curPoint->offset - lastOffset;
            for (int i = 0; i < lastOffset; i++)
            {
                printf(" ");
            }
            printf("[%2d,%d]", curPoint->point->value, curPoint->point->color);
            lastOffset = curPoint->offset + BASE_POINT;
            curPoint = curPoint->next;
        }
        listTemp = listTemp->next;
        printf("\n");
    }
}

void main()
{
    RbTree *rbtree = init_rbtree();

    // RbNode *x = create_rbnode(1);
    // RbNode *y = create_rbnode(2);
    // x->right = y;
    // rbtree->root = x;
    // print_array_to_tree(x);
    // left_rotate(rbtree, x);
    // print_array_to_tree(rbtree->root);
    // right_rotate(rbtree, y);
    // print_array_to_tree(rbtree->root);

    ElementType nodes[9] = {11, 2, 14, 1, 7, 15, 5, 8, 4};
    RbNode *rbnodes[9];
    for (int i = 0; i < 9; i++)
    {
        RbNode *newRbNode = create_rbnode(nodes[i]);
        rbnodes[i] = newRbNode;
        rb_insert(rbtree, newRbNode);
        print_array_to_tree(rbtree->root);
        printf("next=========>\n");
    }

    for (int i = 8; i >= 0; i--)
    {
        rb_delete(rbtree, rbnodes[i]);
        print_array_to_tree(rbtree->root);
        printf("next=========>\n");
    }

    for (int i = 8; i >= 0; i--)
    {
        release_rbnode(rbtree, rbnodes[i], 0);
    }

    release_rbtree(rbtree);
}
